{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Interval to Include Each Query"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #sorting #line-sweep #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #排序 #扫描线 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minInterval"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #包含每个查询的最小区间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二维整数数组 <code>intervals</code> ，其中 <code>intervals[i] = [left<sub>i</sub>, right<sub>i</sub>]</code> 表示第 <code>i</code> 个区间开始于 <code>left<sub>i</sub></code> 、结束于 <code>right<sub>i</sub></code>（包含两侧取值，<strong>闭区间</strong>）。区间的 <strong>长度</strong> 定义为区间中包含的整数数目，更正式地表达是 <code>right<sub>i</sub> - left<sub>i</sub> + 1</code> 。</p>\n",
    "\n",
    "<p>再给你一个整数数组 <code>queries</code> 。第 <code>j</code> 个查询的答案是满足&nbsp;<code>left<sub>i</sub> &lt;= queries[j] &lt;= right<sub>i</sub></code> 的 <strong>长度最小区间 <code>i</code> 的长度</strong> 。如果不存在这样的区间，那么答案是 <code>-1</code> 。</p>\n",
    "\n",
    "<p>以数组形式返回对应查询的所有答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]\n",
    "<strong>输出：</strong>[3,3,1,4]\n",
    "<strong>解释：</strong>查询处理如下：\n",
    "- Query = 2 ：区间 [2,4] 是包含 2 的最小区间，答案为 4 - 2 + 1 = 3 。\n",
    "- Query = 3 ：区间 [2,4] 是包含 3 的最小区间，答案为 4 - 2 + 1 = 3 。\n",
    "- Query = 4 ：区间 [4,4] 是包含 4 的最小区间，答案为 4 - 4 + 1 = 1 。\n",
    "- Query = 5 ：区间 [3,6] 是包含 5 的最小区间，答案为 6 - 3 + 1 = 4 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]\n",
    "<strong>输出：</strong>[2,-1,4,6]\n",
    "<strong>解释：</strong>查询处理如下：\n",
    "- Query = 2 ：区间 [2,3] 是包含 2 的最小区间，答案为 3 - 2 + 1 = 2 。\n",
    "- Query = 19：不存在包含 19 的区间，答案为 -1 。\n",
    "- Query = 5 ：区间 [2,5] 是包含 5 的最小区间，答案为 5 - 2 + 1 = 4 。\n",
    "- Query = 22：区间 [20,25] 是包含 22 的最小区间，答案为 25 - 20 + 1 = 6 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= intervals.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= queries.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>intervals[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= left<sub>i</sub> &lt;= right<sub>i</sub> &lt;= 10<sup>7</sup></code></li>\n",
    "\t<li><code>1 &lt;= queries[j] &lt;= 10<sup>7</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-interval-to-include-each-query](https://leetcode.cn/problems/minimum-interval-to-include-each-query/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-interval-to-include-each-query](https://leetcode.cn/problems/minimum-interval-to-include-each-query/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,4],[2,4],[3,6],[4,4]]\\n[2,3,4,5]', '[[2,3],[2,5],[1,8],[20,25]]\\n[2,19,5,22]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        qindex = list(range(len(queries)))\n",
    "        qindex.sort(key=lambda i: queries[i])\n",
    "        intervals.sort(key=lambda i: i[0])\n",
    "        pq = []\n",
    "        res = [-1] * len(queries)\n",
    "        i = 0\n",
    "        for qi in qindex:\n",
    "            while i < len(intervals) and intervals[i][0] <= queries[qi]:\n",
    "                heappush(pq, (intervals[i][1] - intervals[i][0] + 1, intervals[i][0], intervals[i][1]))\n",
    "                i += 1\n",
    "            while pq and pq[0][2] < queries[qi]:\n",
    "                heappop(pq)\n",
    "            if pq:\n",
    "                res[qi] = pq[0][0]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        qindex=list(range(len(queries)))\n",
    "        qindex.sort(key=lambda x: queries[x])\n",
    "        intervals.sort(key=lambda x:x[0])\n",
    "        pq=[]\n",
    "        length=len(intervals)\n",
    "        i=0\n",
    "        result=[-1]*len(queries)\n",
    "        for qi in qindex:\n",
    "            while i<length and intervals[i][0]<=queries[qi]:\n",
    "                heappush(pq,(intervals[i][1]-intervals[i][0]+1,intervals[i][0],intervals[i][1]))\n",
    "                i+=1\n",
    "            while pq and pq[0][2]<queries[qi]:\n",
    "                heappop(pq)\n",
    "            if pq:\n",
    "                result[qi]=pq[0][0]\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        qindex = list(range(len(queries)))\n",
    "        qindex.sort(key = lambda x: queries[x])\n",
    "\n",
    "        intervals.sort(key = lambda x : x[0])\n",
    "        pq = []\n",
    "        res= [-1] * len(queries)\n",
    "        i = 0 \n",
    "        for qi in qindex:\n",
    "            while i < len(intervals) and intervals[i][0] <= queries[qi]:\n",
    "                heappush(pq,(intervals[i][1] - intervals[i][0]+1,intervals[i][0],intervals[i][1] ))\n",
    "                i+=1\n",
    "            while pq and pq[0][2] < queries[qi]:\n",
    "                heappop(pq)\n",
    "            if pq:\n",
    "                res[qi] = pq[0][0]\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        # 231009 note\n",
    "        # 参考上次提交记录：排序+最小堆\n",
    "        # 首先能想到需要对intervals和queries排序，然后从小到大遍历查询的qidx\n",
    "        # 对每个qidx，需要找到包含qidx的长度最小的区间，因此可以采用最小堆来存储，排序的第一要求为长度\n",
    "        # 1 首先先将所有包含qidx的区间都加入到最小堆当中（都是当前满足条件的），即对intervals从小到大加入，直到不满足条件。入堆条件：intervals[i][0] <= qidx（区间左端点小于等于qidx）  \n",
    "        # 2 最小堆当中会存在一些之间满足条件（包含之前的qidx）但已经不包含当前qidx的元素仍未弹出，因此需要从堆顶弹出所有不包含qidx的区间，此时堆顶元素即为包含qidx的长度最小的区间。出堆条件：区间右端点小于qidx\n",
    "        # 3 如果堆顶有元素，则得到对应的区间长度，否则-1\n",
    "        # 由于出堆时需要比较右端点，因此堆中元素需要存储区间长度和右端点值\n",
    "\n",
    "        intervals.sort()\n",
    "        qindex = [i for i in range(len(queries))]\n",
    "        qindex.sort(key=lambda x: queries[x])\n",
    "        # qpairs = sorted(zip(queries, [i for i in range(len(queries))]))\n",
    "        heap = []  # (区间长度，右端点值)\n",
    "        i = 0  # intervals的idx\n",
    "        n = len(intervals)\n",
    "        ans = [-1]*len(queries)\n",
    "        # for qidx, qi in qpairs:\n",
    "        for j in qindex:\n",
    "            qidx = queries[j]\n",
    "            # 加入所有包含qidx的区间\n",
    "            while i < n and intervals[i][0] <= qidx:\n",
    "                heapq.heappush(heap, (intervals[i][1]-intervals[i][0]+1, intervals[i][1]))\n",
    "                i += 1\n",
    "            # 弹出不包含qidx的区间\n",
    "            while heap and heap[0][1] < qidx:\n",
    "                heapq.heappop(heap)\n",
    "            if heap:\n",
    "                ans[j] = heap[0][0]\n",
    "                # ans[qi] = heap[0][0]\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        qindex = list(range(len(queries)))\n",
    "        qindex.sort(key=lambda i: queries[i])\n",
    "        intervals.sort(key=lambda x: x[0])\n",
    "        ans = [-1]*len(queries)\n",
    "        pq = []\n",
    "        i = 0\n",
    "        for qi in qindex:\n",
    "            while i<len(intervals) and intervals[i][0]<=queries[qi]:\n",
    "                heappush(pq,(intervals[i][1]-intervals[i][0]+1, intervals[i][0], intervals[i][1]))\n",
    "                i += 1\n",
    "            while pq and pq[0][2]<queries[qi]:\n",
    "                heappop(pq)\n",
    "            if pq:\n",
    "                ans[qi] = pq[0][0]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        n = len(queries)\n",
    "        ix = sorted(range(n),key=lambda x:queries[x])\n",
    "        i = 0\n",
    "        intervals.sort()\n",
    "        m = len(intervals)\n",
    "        ans = [-1] * n \n",
    "        pq = []\n",
    "        for q in ix:\n",
    "            while i < m and intervals[i][0] <= queries[q]:\n",
    "                heappush(pq, (intervals[i][1] - intervals[i][0] + 1,intervals[i][1]))\n",
    "                i += 1\n",
    "            while pq and pq[0][1] < queries[q]:\n",
    "                heappop(pq)\n",
    "            if pq:\n",
    "                ans[q] = pq[0][0]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        qindex = list(range(len(queries)))\n",
    "        qindex.sort(key=lambda i: queries[i])\n",
    "        intervals.sort(key=lambda i: i[0])\n",
    "        pq = []\n",
    "        res = [-1] * len(queries)\n",
    "        i = 0\n",
    "        for qi in qindex:\n",
    "            while i < len(intervals) and intervals[i][0] <= queries[qi]:\n",
    "                heappush(pq, (intervals[i][1] - intervals[i][0] + 1, intervals[i][0], intervals[i][1]))\n",
    "                i += 1\n",
    "            while pq and pq[0][2] < queries[qi]:\n",
    "                heappop(pq)\n",
    "            if pq:\n",
    "                res[qi] = pq[0][0]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        n = len(intervals)\n",
    "        qindex = sorted(range(len(queries)),key=lambda i:queries[i])\n",
    "        intervals.sort(key=lambda i:i[0])\n",
    "        dp = [-1]*len(queries)\n",
    "        i = 0\n",
    "        res = []\n",
    "        for qi in qindex:\n",
    "            while i < n and intervals[i][0] <= queries[qi]:\n",
    "                heappush(res,(intervals[i][1]-intervals[i][0]+1,intervals[i][0],intervals[i][1]))\n",
    "                i += 1\n",
    "            while res and queries[qi] > res[0][2]:\n",
    "                heappop(res)\n",
    "            if res:\n",
    "                dp[qi] = res[0][0]\n",
    "        return dp "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        qindex = list(range(len(queries)))\n",
    "        qindex.sort(key=lambda i: queries[i])\n",
    "        intervals.sort(key=lambda i: i[0])\n",
    "        pq = []\n",
    "        res = [-1] * len(queries)\n",
    "        i = 0\n",
    "        for qi in qindex:\n",
    "            while i < len(intervals) and intervals[i][0] <= queries[qi]:\n",
    "                heappush(pq, (intervals[i][1] - intervals[i][0] + 1, intervals[i][0], intervals[i][1]))\n",
    "                i += 1\n",
    "            while pq and pq[0][2] < queries[qi]:\n",
    "                heappop(pq)\n",
    "            if pq:\n",
    "                res[qi] = pq[0][0]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        qindex = list(range(len(queries)))\n",
    "        qindex.sort(key=lambda i: queries[i])\n",
    "        intervals.sort(key=lambda i: i[0])\n",
    "        pq = []\n",
    "        res = [-1] * len(queries)\n",
    "        i = 0\n",
    "        for qi in qindex:\n",
    "            while i < len(intervals) and intervals[i][0] <= queries[qi]:\n",
    "                heappush(pq, (intervals[i][1] - intervals[i][0] + 1, intervals[i][0], intervals[i][1]))\n",
    "                i += 1\n",
    "            while pq and pq[0][2] < queries[qi]:\n",
    "                heappop(pq)\n",
    "            if pq:\n",
    "                res[qi] = pq[0][0]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        n = len(intervals)\n",
    "        qindex = sorted(range(len(queries)),key=lambda i:queries[i])\n",
    "        intervals.sort(key=lambda i:i[0])\n",
    "        dp = [-1]*len(queries)\n",
    "        i = 0\n",
    "        res = []\n",
    "        for qi in qindex:\n",
    "            while i < n and intervals[i][0] <= queries[qi]:\n",
    "                heappush(res,(intervals[i][1]-intervals[i][0]+1,intervals[i][0],intervals[i][1]))\n",
    "                i += 1\n",
    "            while res and queries[qi] > res[0][2]:\n",
    "                heappop(res)\n",
    "            if res:\n",
    "                dp[qi] = res[0][0]\n",
    "        return dp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# File       : bak.py\n",
    "# Time       ：2023/9/21 19:43\n",
    "# Author     ：author name\n",
    "# version    ：python 3\n",
    "# Description：\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        qindex = list(range(len(queries)))\n",
    "        qindex.sort(key=lambda i: queries[i])\n",
    "        intervals.sort(key=lambda i: i[0])\n",
    "        \n",
    "        res = [-1] * len(queries)\n",
    "        i = 0\n",
    "        pq = []\n",
    "        for qi in qindex:\n",
    "            while i < len(intervals) and intervals[i][0] <= queries[qi]:\n",
    "                heappush(pq, (intervals[i][1] - intervals[i][0] + 1, intervals[i][1]))\n",
    "                i += 1\n",
    "            while pq and pq[0][1] < queries[qi]:\n",
    "                heappop(pq)\n",
    "            if pq:\n",
    "                res[qi] = pq[0][0]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        qindex = list(range(len(queries)))\n",
    "        qindex.sort(key=lambda i: queries[i])\n",
    "        intervals.sort(key=lambda i: i[0])\n",
    "        pq = []\n",
    "        res = [-1] * len(queries)\n",
    "        i = 0\n",
    "        for qi in qindex:\n",
    "            while i < len(intervals) and intervals[i][0] <= queries[qi]:\n",
    "                heappush(pq, (intervals[i][1] - intervals[i][0] + 1, intervals[i][0], intervals[i][1]))\n",
    "                i += 1\n",
    "            while pq and pq[0][2] < queries[qi]:\n",
    "                heappop(pq)\n",
    "            if pq:\n",
    "                res[qi] = pq[0][0]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        qindex = list(range(len(queries)))\n",
    "        qindex.sort(key=lambda i: queries[i])\n",
    "        intervals.sort(key=lambda i: i[0])\n",
    "        pq = []\n",
    "        res = [-1] * len(queries)\n",
    "        i = 0\n",
    "        for qi in qindex:\n",
    "            while i < len(intervals) and intervals[i][0] <= queries[qi]:\n",
    "                heappush(pq, (intervals[i][1] - intervals[i][0] + 1, intervals[i][0], intervals[i][1]))\n",
    "                i += 1\n",
    "            while pq and pq[0][2] < queries[qi]:\n",
    "                heappop(pq)\n",
    "            if pq:\n",
    "                res[qi] = pq[0][0]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        n = len(intervals)\n",
    "        qindex = sorted(range(len(queries)),key=lambda i:queries[i])\n",
    "        intervals.sort(key=lambda i:i[0])\n",
    "        dp = [-1]*len(queries)\n",
    "        i = 0\n",
    "        res = []\n",
    "        for qi in qindex:\n",
    "            while i < n and intervals[i][0] <= queries[qi]:\n",
    "                heappush(res,(intervals[i][1]-intervals[i][0]+1,intervals[i][0],intervals[i][1]))\n",
    "                i += 1\n",
    "            while res and queries[qi] > res[0][2]:\n",
    "                heappop(res)\n",
    "            if res:\n",
    "                dp[qi] = res[0][0]\n",
    "        return dp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        result, m, pq, idx, i = [-1] * (n := len(queries)), len(intervals), [], list(range(n)), 0\n",
    "        idx.sort(key=lambda x: queries[x])\n",
    "        intervals.sort(key=lambda x: x[0])\n",
    "        for x in idx:\n",
    "            while i < m and intervals[i][0] <= queries[x]:\n",
    "                heappush(pq, (intervals[i][1] - intervals[i][0] + 1, intervals[i][0], intervals[i][1]))\n",
    "                i += 1\n",
    "            while pq and pq[0][2] < queries[x]:\n",
    "                heappop(pq)\n",
    "            if pq:\n",
    "                result[x] = pq[0][0]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m = len(intervals)\n",
    "        n = len(queries)\n",
    "        dp = [-1]*n\n",
    "        qindex = list(range(n))\n",
    "        qindex.sort(key=lambda i:queries[i])\n",
    "        intervals.sort(key=lambda i:[i][0])\n",
    "        i = 0\n",
    "        res = []\n",
    "        for qi in qindex:\n",
    "            while i<m and intervals[i][0] <= queries[qi]:\n",
    "                heappush(res,(intervals[i][1]-intervals[i][0]+1,intervals[i][0],intervals[i][1]))\n",
    "                i += 1\n",
    "            while res and res[0][2] < queries[qi]:\n",
    "                heappop(res)\n",
    "            if res:\n",
    "                dp[qi] = res[0][0]\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "\n",
    "        qindex = list(range(len(queries)))\n",
    "        qindex = sorted(qindex, key=lambda i: queries[i])\n",
    "        intervals = sorted(intervals, key=lambda i: i[0])\n",
    "\n",
    "        prior_queue = []\n",
    "        res = [-1] * len(queries)\n",
    "\n",
    "        idx = 0\n",
    "        for qi in qindex:\n",
    "            while idx < len(intervals) and intervals[idx][0] <= queries[qi]:\n",
    "                heapq.heappush(prior_queue, (intervals[idx][1] - intervals[idx][0] + 1, intervals[idx][0], intervals[idx][1]))\n",
    "                idx += 1\n",
    "            while prior_queue and prior_queue[0][2] < queries[qi]:\n",
    "                heapq.heappop(prior_queue)\n",
    "            if prior_queue:\n",
    "                res[qi] = prior_queue[0][0]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        lq = len(queries)\n",
    "        sq = sorted(range(lq), key=lambda i: queries[i])\n",
    "        ans = [-1] * lq\n",
    "        \n",
    "        intervals.sort(key=itemgetter(0))\n",
    "        intervals.append([inf, inf])\n",
    "\n",
    "        idx = 0\n",
    "        heap = [(inf, inf)]\n",
    "\n",
    "        for i in sq:\n",
    "            q = queries[i]\n",
    "\n",
    "            while intervals[idx][0] <= q:\n",
    "                l, r = intervals[idx]\n",
    "                heappush(heap, (r - l + 1, r))\n",
    "                idx += 1\n",
    "            \n",
    "            while heap[0][1] < q:\n",
    "                heappop(heap)\n",
    "            \n",
    "            if heap[0][0] != inf:\n",
    "                ans[i] = heap[0][0]\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(intervals), len(queries)\n",
    "\n",
    "        intervals.sort(key=lambda x: x[1] - x[0])\n",
    "        queries = SortedList([(q, i) for i, q in enumerate(queries)])\n",
    "\n",
    "\n",
    "        ans = [-1] * n\n",
    "\n",
    "        for l, r in intervals:\n",
    "            length = r - l + 1\n",
    "            idx = bisect_left(queries, (l, 0))\n",
    "\n",
    "            while idx <len(queries) and queries[idx][0] <= r:\n",
    "                ans[queries[idx][1]] = length\n",
    "                queries.pop(idx)\n",
    "                \n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        qindex = list(range(len(queries)))\n",
    "        qindex.sort(key=lambda i: queries[i])\n",
    "        intervals.sort(key=lambda i: i[0])\n",
    "        print(intervals)\n",
    "\n",
    "        res = [-1] * len(queries)\n",
    "        i = 0\n",
    "        # pq = []\n",
    "        # # heappush heappop 这两个 表示创建一个小顶堆，想表示\n",
    "        # for qi in qindex:\n",
    "        #     while i < len(intervals) and intervals[i][0] <= queries[qi]:\n",
    "        #         heappush(pq, (intervals[i][1] - intervals[i][0] + 1, intervals[i][1]))\n",
    "        #         i += 1\n",
    "        #     while pq and pq[0][1] < queries[qi]:\n",
    "        #         heappop(pq)\n",
    "        #     if pq:\n",
    "        #         res[qi] = pq[0][0]\n",
    "        # return res\n",
    "\n",
    "        pq = SortedList([])\n",
    "        for qi in qindex:\n",
    "            while i < len(intervals) and intervals[i][0] <= queries[qi]:\n",
    "                pq.add((intervals[i][1] - intervals[i][0] + 1, intervals[i][1]))\n",
    "                i += 1\n",
    "            while pq and pq[0][1] < queries[qi]:\n",
    "                pq.remove(pq[0])\n",
    "            if pq:\n",
    "                res[qi] = pq[0][0]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import *\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        intervals.sort()\n",
    "        i = 0\n",
    "        queries = sorted([(x, i) for i, x in enumerate(queries)])\n",
    "        sl, sl2 = SortedList(), SortedList()\n",
    "        n = len(queries)\n",
    "        ans = [-1] * n\n",
    "        for q, j in queries:\n",
    "            while sl and sl[0][0] < q:\n",
    "                sl2.remove((sl[0][0] - sl[0][1] + 1))\n",
    "                sl.pop(0) \n",
    "     \n",
    "            while i < len(intervals):\n",
    "                if intervals[i][1] < q:\n",
    "                    i += 1\n",
    "                elif intervals[i][0] <= q <= intervals[i][1]:\n",
    "                    sl.add((intervals[i][1], intervals[i][0]))\n",
    "                    sl2.add(intervals[i][1] - intervals[i][0] + 1)\n",
    "                    i += 1\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            \n",
    "            if sl2: ans[j] = sl2[0]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, n) -> None:\n",
    "        self.fa = [i for i in range(n)]\n",
    "        self.count = n\n",
    "\n",
    "\n",
    "    def find(self, x):\n",
    "        x_copy = x\n",
    "        while x_copy != self.fa[x_copy]:\n",
    "            x_copy  = self.fa[x_copy]\n",
    "        root= x_copy\n",
    "        x_copy = x\n",
    "        while x_copy != root:\n",
    "            self.fa[x_copy] = root\n",
    "            x_copy = self.fa[x_copy]\n",
    "\n",
    "        return self.fa[x]\n",
    "    \n",
    "    \n",
    "    def merge(self, x, y):\n",
    "        self.fa[x] = self.find(y)\n",
    "        self.count -= 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        queries = [ (n, i) for i, n in enumerate(queries)]\n",
    "        intervals.sort(key=lambda x:x[1]-x[0])\n",
    "        queries.sort()\n",
    "        n = len(queries)\n",
    "        dsu = DSU(n+1)\n",
    "        ans = [-1]*n\n",
    "        for l, r in intervals:\n",
    "            if dsu.count == 1:\n",
    "                break\n",
    "            q = bisect_left(queries, (l, 0))\n",
    "            while q < n and queries[q][0] <= r:\n",
    "                q = dsu.find(q)\n",
    "                if q == n:\n",
    "                    break\n",
    "                if  l<= queries[q][0] <= r:\n",
    "                    ans[queries[q][1]] = r - l + 1\n",
    "                    if q <= n:\n",
    "                        dsu.merge(q, q+1)\n",
    "                q += 1\n",
    "        return ans\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, n) -> None:\n",
    "        self.fa = [i for i in range(n)]\n",
    "        self.count = n\n",
    "\n",
    "\n",
    "    def find(self, x):\n",
    "        x_copy = x\n",
    "        while x_copy != self.fa[x_copy]:\n",
    "            x_copy  = self.fa[x_copy]\n",
    "        root= x_copy\n",
    "        x_copy = x\n",
    "        while x_copy != root:\n",
    "            self.fa[x_copy] = root\n",
    "            x_copy = self.fa[x_copy]\n",
    "\n",
    "        return self.fa[x]\n",
    "    \n",
    "    \n",
    "    def merge(self, x, y):\n",
    "        self.fa[x] = self.find(y)\n",
    "        self.count -= 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        queries = [ (n, i) for i, n in enumerate(queries)]\n",
    "        intervals.sort(key=lambda x:x[1]-x[0])\n",
    "        queries.sort()\n",
    "        n = len(queries)\n",
    "        dsu = DSU(n+1)\n",
    "        ans = [-1]*n\n",
    "        for l, r in intervals:\n",
    "            if dsu.count == 1:\n",
    "                break\n",
    "            q = bisect_left(queries, (l, 0))\n",
    "            while q < n and queries[q][0] <= r:\n",
    "                q = dsu.find(q)\n",
    "                if q == n:\n",
    "                    break\n",
    "                if  l<= queries[q][0] <= r:\n",
    "                    ans[queries[q][1]] = r - l + 1\n",
    "                    if q <= n:\n",
    "                        dsu.merge(q, q+1)\n",
    "                q += 1\n",
    "        return ans\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, n) -> None:\n",
    "        self.fa = [i for i in range(n)]\n",
    "        self.count = n\n",
    "\n",
    "\n",
    "    def find(self, x):\n",
    "        x_copy = x\n",
    "        while x_copy != self.fa[x_copy]:\n",
    "            x_copy  = self.fa[x_copy]\n",
    "        root= x_copy\n",
    "        x_copy = x\n",
    "        while x_copy != root:\n",
    "            self.fa[x_copy] = root\n",
    "            x_copy = self.fa[x_copy]\n",
    "\n",
    "        return self.fa[x]\n",
    "    \n",
    "    \n",
    "    def merge(self, x, y):\n",
    "        self.fa[x] = self.find(y)\n",
    "        self.count -= 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        queries = [ (n, i) for i, n in enumerate(queries)]\n",
    "        intervals.sort(key=lambda x:x[1]-x[0])\n",
    "        queries_bk = SortedList(queries)\n",
    "        n = len(queries)\n",
    "        dsu = DSU(n+1)\n",
    "        ans = [-1]*n\n",
    "        for l, r in intervals:\n",
    "       \n",
    "            q = queries_bk.bisect_left((l, -1))\n",
    "            q = dsu.find(q)\n",
    "            while q < n and queries_bk[q][0] <= r:\n",
    "                ans[queries_bk[q][1]] = r - l + 1\n",
    "                dsu.merge(q, q+1)\n",
    "                q = dsu.find(q+1)\n",
    "               \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, n) -> None:\n",
    "        self.fa = [i for i in range(n)]\n",
    "        # self.count = n\n",
    "\n",
    "\n",
    "    def find(self, x):\n",
    "        x_copy = x\n",
    "        while x_copy != self.fa[x_copy]:\n",
    "            x_copy  = self.fa[x_copy]\n",
    "        root= x_copy\n",
    "        x_copy = x\n",
    "        while x_copy != root:\n",
    "            self.fa[x_copy] = root\n",
    "            x_copy = self.fa[x_copy]\n",
    "\n",
    "        return self.fa[x]\n",
    "    \n",
    "    \n",
    "    def merge(self, x, y):\n",
    "        self.fa[x] = self.find(y)\n",
    "        # self.count -= 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        queries = [ (n, i) for i, n in enumerate(queries)]\n",
    "        intervals.sort(key=lambda x:x[1]-x[0])\n",
    "        queries_bk = SortedList(queries)\n",
    "        n = len(queries)\n",
    "        dsu = DSU(n+1)\n",
    "        ans = [-1]*n\n",
    "        for l, r in intervals:\n",
    "       \n",
    "            q = queries_bk.bisect_left((l, -1))\n",
    "            q = dsu.find(q)\n",
    "            while q < n and queries_bk[q][0] <= r:\n",
    "                ans[queries_bk[q][1]] = r - l + 1\n",
    "                dsu.merge(q, q+1)\n",
    "                q = dsu.find(q+1)\n",
    "                # q += 1\n",
    "               \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, n) -> None:\n",
    "        self.fa = [i for i in range(n)]\n",
    "        self.count = n\n",
    "\n",
    "\n",
    "    def find(self, x):\n",
    "        x_copy = x\n",
    "        while x_copy != self.fa[x_copy]:\n",
    "            x_copy  = self.fa[x_copy]\n",
    "        root= x_copy\n",
    "        x_copy = x\n",
    "        while x_copy != root:\n",
    "            self.fa[x_copy] = root\n",
    "            x_copy = self.fa[x_copy]\n",
    "\n",
    "        return self.fa[x]\n",
    "    \n",
    "    \n",
    "    def merge(self, x, y):\n",
    "        self.fa[x] = self.find(y)\n",
    "        self.count -= 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        queries = [ (n, i) for i, n in enumerate(queries)]\n",
    "        intervals.sort(key=lambda x:x[1]-x[0])\n",
    "        queries_bk = SortedList(queries)\n",
    "        n = len(queries)\n",
    "        dsu = DSU(n+1)\n",
    "        ans = [-1]*n\n",
    "        for l, r in intervals:\n",
    "       \n",
    "            q = queries_bk.bisect_left((l, -1))\n",
    "            q = dsu.find(q)\n",
    "            while q < n and queries_bk[q][0] <= r:\n",
    "                ans[queries_bk[q][1]] = r - l + 1\n",
    "                dsu.merge(q, q+1)\n",
    "                q = dsu.find(q+1)\n",
    "                # q += 1\n",
    "               \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, n) -> None:\n",
    "        self.fa = [i for i in range(n)]\n",
    "        self.count = n\n",
    "\n",
    "\n",
    "    def find(self, x):\n",
    "        x_copy = x\n",
    "        while x_copy != self.fa[x_copy]:\n",
    "            x_copy  = self.fa[x_copy]\n",
    "        root= x_copy\n",
    "        x_copy = x\n",
    "        while x_copy != root:\n",
    "            self.fa[x_copy] = root\n",
    "            x_copy = self.fa[x_copy]\n",
    "\n",
    "        return self.fa[x]\n",
    "    \n",
    "    \n",
    "    def merge(self, x, y):\n",
    "        self.fa[x] = self.find(y)\n",
    "        self.count -= 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        queries = [ (n, i) for i, n in enumerate(queries)]\n",
    "        intervals.sort(key=lambda x:x[1]-x[0])\n",
    "        queries_bk = SortedList(queries)\n",
    "        n = len(queries)\n",
    "        dsu = DSU(n+1)\n",
    "        ans = [-1]*n\n",
    "        for l, r in intervals:\n",
    "            if dsu.count == 1:\n",
    "                break\n",
    "            q = queries_bk.bisect_left((l, 0))\n",
    "            while q < n and queries_bk[q][0] <= r:\n",
    "                q = dsu.find(q)\n",
    "                if q == n:\n",
    "                    break\n",
    "                if  l<= queries_bk[q][0] <= r:\n",
    "                    ans[queries_bk[q][1]] = r - l + 1\n",
    "                    if q <= n:\n",
    "                        dsu.merge(q, q+1)\n",
    "                q += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, n) -> None:\n",
    "        self.fa = [i for i in range(n)]\n",
    "        self.count = n\n",
    "\n",
    "\n",
    "    def find(self, x):\n",
    "        x_copy = x\n",
    "        while x_copy != self.fa[x_copy]:\n",
    "            x_copy  = self.fa[x_copy]\n",
    "        root= x_copy\n",
    "        x_copy = x\n",
    "        while x_copy != root:\n",
    "            self.fa[x_copy] = root\n",
    "            x_copy = self.fa[x_copy]\n",
    "\n",
    "        return self.fa[x]\n",
    "    \n",
    "    \n",
    "    def merge(self, x, y):\n",
    "        self.fa[x] = self.find(y)\n",
    "        self.count -= 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        queries = [ (n, i) for i, n in enumerate(queries)]\n",
    "        intervals.sort(key=lambda x:x[1]-x[0])\n",
    "        queries_bk = SortedList(queries)\n",
    "        n = len(queries)\n",
    "        dsu = DSU(n+1)\n",
    "        ans = [-1]*n\n",
    "        for l, r in intervals:\n",
    "            if dsu.count == 1:\n",
    "                break\n",
    "            q = queries_bk.bisect_left((l, 0))\n",
    "            while q < n and queries_bk[q][0] <= r:\n",
    "                q = dsu.find(q)\n",
    "                if q == n:\n",
    "                    break\n",
    "                if  l<= queries_bk[q][0] <= r:\n",
    "                    ans[queries_bk[q][1]] = r - l + 1\n",
    "                    if q <= n:\n",
    "                        dsu.merge(q, q+1)\n",
    "                q += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, n) -> None:\n",
    "        self.fa = [i for i in range(n)]\n",
    "        # self.count = n\n",
    "\n",
    "\n",
    "    def find(self, x):\n",
    "        x_copy = x\n",
    "        while x_copy != self.fa[x_copy]:\n",
    "            x_copy  = self.fa[x_copy]\n",
    "        root= x_copy\n",
    "        x_copy = x\n",
    "        while x_copy != root:\n",
    "            self.fa[x_copy] = root\n",
    "            x_copy = self.fa[x_copy]\n",
    "\n",
    "        return self.fa[x]\n",
    "    \n",
    "    \n",
    "    def merge(self, x, y):\n",
    "        self.fa[x] = self.find(y)\n",
    "        # self.count -= 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        queries = [ (n, i) for i, n in enumerate(queries)]\n",
    "        intervals.sort(key=lambda x:x[1]-x[0])\n",
    "        queries_bk = SortedList(queries)\n",
    "        n = len(queries)\n",
    "        dsu = DSU(n+1)\n",
    "        ans = [-1]*n\n",
    "        for l, r in intervals:\n",
    "       \n",
    "            q = queries_bk.bisect_left((l, -1))\n",
    "            q = dsu.find(q)\n",
    "            while q < n and queries_bk[q][0] <= r:\n",
    "                ans[queries_bk[q][1]] = r - l + 1\n",
    "                dsu.merge(q, q+1)\n",
    "                q = dsu.find(q+1)\n",
    "                # q += 1\n",
    "               \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        intervals.sort()\n",
    "        memo = {}\n",
    "        i = 0\n",
    "        heap = []\n",
    "\n",
    "        for q in sorted(queries):\n",
    "            while i < len(intervals) and intervals[i][0] <= q:\n",
    "                l, r = intervals[i]\n",
    "                heappush(heap, (r - l + 1, r))\n",
    "                i += 1\n",
    "            \n",
    "            while heap and heap[0][1] < q:\n",
    "                heappop(heap)\n",
    "            \n",
    "            memo[q] = heap[0][0] if heap else -1\n",
    "        \n",
    "        return [memo[q] for q in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappush, heappop\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        intervals.sort()\n",
    "        sorted_queries = sorted(queries)\n",
    "        min_heap = []\n",
    "        result = {}\n",
    "        i = 0\n",
    "        for q in sorted_queries:\n",
    "            while i < len(intervals) and intervals[i][0] <= q:\n",
    "                interval_size = intervals[i][1] - intervals[i][0] + 1\n",
    "                heappush(min_heap, (interval_size, intervals[i][1]))\n",
    "                i += 1\n",
    "            while min_heap and min_heap[0][1] < q:\n",
    "                heappop(min_heap)\n",
    "            result[q] = min_heap[0][0] if min_heap else -1\n",
    "        return [result[q] for q in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        intervals.sort()\n",
    "        minHeap = []\n",
    "        res = {}\n",
    "        i = 0\n",
    "        for q in sorted(queries):\n",
    "            while i < len(intervals) and intervals[i][0] <= q:\n",
    "                l, r = intervals[i]\n",
    "                heapq.heappush(minHeap, (r - l + 1, r))\n",
    "                i += 1\n",
    "\n",
    "            while minHeap and minHeap[0][1] < q:\n",
    "                heapq.heappop(minHeap)\n",
    "            res[q] = minHeap[0][0] if minHeap else -1\n",
    "        return [res[q] for q in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        # nums = {x: i for i, x in enumerate(queries)} # wrong\n",
    "        # # since x as key for dic can't be duplicates\n",
    "        # for [7,9,3,9,3] -> {7: 0, 9: 3, 3: 4}\n",
    "        # res = [-1] * len(queries) wrong\n",
    "        res = {} # instead\n",
    "        intervals.sort()\n",
    "        heap = []\n",
    "       \n",
    "        i = 0\n",
    "        n = len(intervals)\n",
    "        for q in sorted(queries):\n",
    "            while i < n and intervals[i][0] <= q:\n",
    "                x, y = intervals[i]\n",
    "                heapq.heappush(heap, (y -x + 1, y))\n",
    "                i += 1 # SUPER important i+1\n",
    "            while heap and q > heap[0][1]: # heap and\n",
    "                heapq.heappop(heap)\n",
    "            if heap:\n",
    "                res[q] = heap[0][0] # instead\n",
    "            else:\n",
    "                res[q] = -1\n",
    "        return [res[q] for q in queries]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        # 231009 note\n",
    "        # 参考上次提交记录：排序+最小堆\n",
    "        # 首先能想到需要对intervals和queries排序，然后从小到大遍历查询的qidx\n",
    "        # 对每个qidx，需要找到包含qidx的长度最小的区间，因此可以采用最小堆来存储，排序的第一要求为长度\n",
    "        # 1 首先先将所有包含qidx的区间都加入到最小堆当中（都是当前满足条件的），即对intervals从小到大加入，直到不满足条件。入堆条件：intervals[i][0] <= qidx（区间左端点小于等于qidx）  \n",
    "        # 2 最小堆当中会存在一些之间满足条件（包含之前的qidx）但已经不包含当前qidx的元素仍未弹出，因此需要从堆顶弹出所有不包含qidx的区间，此时堆顶元素即为包含qidx的长度最小的区间。出堆条件：区间右端点小于qidx\n",
    "        # 3 如果堆顶有元素，则得到对应的区间长度，否则-1\n",
    "        # 由于出堆时需要比较右端点，因此堆中元素需要存储区间长度和右端点值\n",
    "\n",
    "        intervals.sort()\n",
    "        qpairs = sorted(zip(queries, [i for i in range(len(queries))]))\n",
    "        heap = []  # (区间长度，右端点值)\n",
    "        i = 0  # intervals的idx\n",
    "        n = len(intervals)\n",
    "        ans = [-1]*len(queries)\n",
    "        for qidx, qi in qpairs:\n",
    "            # 加入所有包含qidx的区间\n",
    "            while i < n and intervals[i][0] <= qidx:\n",
    "                heapq.heappush(heap, (intervals[i][1]-intervals[i][0]+1, intervals[i][1]))\n",
    "                i += 1\n",
    "            # 弹出不包含qidx的区间\n",
    "            while heap and heap[0][1] < qidx:\n",
    "                heapq.heappop(heap)\n",
    "            if heap:\n",
    "                ans[qi] = heap[0][0]\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "      intervals.sort()\n",
    "      minHeap = []\n",
    "      i, res = 0, {}\n",
    "\n",
    "      for q in sorted(list(set(queries))):\n",
    "        while i < len(intervals) and intervals[i][0] <= q:\n",
    "          [l, r] = intervals[i]\n",
    "          heapq.heappush(minHeap, (r - l + 1, r))\n",
    "          i += 1\n",
    "\n",
    "        while len(minHeap) > 0 and minHeap[0][1] < q:\n",
    "          heapq.heappop(minHeap)\n",
    "\n",
    "        res[q] = minHeap[0][0] if minHeap else -1\n",
    "\n",
    "      return [res[q] for q in queries]\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "      intervals.sort()\n",
    "      minHeap = []\n",
    "      i, res = 0, {}\n",
    "\n",
    "      for q in sorted(list(set(queries))):\n",
    "        while i < len(intervals) and intervals[i][0] <= q:\n",
    "          [l, r] = intervals[i]\n",
    "          heapq.heappush(minHeap, (r - l + 1, r))\n",
    "          i += 1\n",
    "\n",
    "        while len(minHeap) > 0 and minHeap[0][1] < q:\n",
    "          heapq.heappop(minHeap)\n",
    "        \n",
    "        if len(minHeap) == 0:\n",
    "          res[q] = -1\n",
    "        else:\n",
    "          res[q] = minHeap[0][0]\n",
    "\n",
    "      return [res[q] for q in queries]\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        intervals.sort()\n",
    "        i, res = 0, defaultdict(int)\n",
    "        pq = []\n",
    "        for q in sorted(queries):\n",
    "            while i < len(intervals) and intervals[i][0] <= q:\n",
    "                heappush(pq, [intervals[i][1] - intervals[i][0] + 1, intervals[i][1]])\n",
    "                i += 1\n",
    "            while pq and pq[0][1] < q:\n",
    "                heappop(pq)\n",
    "            res[q] = pq[0][0] if pq else -1\n",
    "        return [res[q] for q in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        n, m = len(intervals), len(queries)\n",
    "        intervals.sort()\n",
    "        queries = sorted((x, i) for i, x in enumerate(queries))\n",
    "        ans = [-1] * m\n",
    "        pq = []\n",
    "        i = 0\n",
    "        for x, j in queries:\n",
    "            while i < n and intervals[i][0] <= x:\n",
    "                a, b = intervals[i]\n",
    "                heappush(pq, (b - a + 1, b))\n",
    "                i += 1\n",
    "            while pq and pq[0][1] < x:\n",
    "                heappop(pq)\n",
    "            if pq:\n",
    "                ans[j] = pq[0][0]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        n, m = len(intervals), len(queries)\n",
    "        intervals.sort()\n",
    "        queries = sorted((x, i) for i, x in enumerate(queries))\n",
    "        ans = [-1] * m\n",
    "        pq = []\n",
    "        i = 0\n",
    "        for x, j in queries:\n",
    "            while i < n and intervals[i][0] <= x:\n",
    "                a,b = intervals[i]\n",
    "                heappush(pq, (b-a+1, b))\n",
    "                i+=1\n",
    "            while pq and pq[0][1] < x:\n",
    "                heappop(pq)\n",
    "            if pq:\n",
    "                ans[j] = pq[0][0]\n",
    "        return ans     \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        qs = sorted((q, i) for i, q in enumerate(queries))\n",
    "        intervals.sort()\n",
    "        n, m = len(intervals), len(queries)\n",
    "        res = [-1] * m\n",
    "        h = []\n",
    "        i = 0\n",
    "        for q, qi in qs:\n",
    "            while i < n and intervals[i][0] <= q:\n",
    "                a, b = intervals[i]\n",
    "                heappush(h, (b - a + 1, b))\n",
    "                i += 1\n",
    "            while h and h[0][1] < q:\n",
    "                heappop(h)\n",
    "            if h:\n",
    "                res[qi] = h[0][0]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        intervals.sort()\n",
    "        queries = sorted(((x, i) for i, x in enumerate(queries)))  # item is [val, idx]\n",
    "\n",
    "\n",
    "        ans = [-1] * len(queries)\n",
    "        pq = []  # item is [size, right]\n",
    "        i = 0\n",
    "\n",
    "        for x, j in queries:\n",
    "\n",
    "            # 收集候选者\n",
    "            while i < len(intervals) and intervals[i][0] <= x:\n",
    "                l, r = intervals[i]\n",
    "                heapq.heappush(pq, (r - l + 1, r))\n",
    "                i += 1\n",
    "\n",
    "            while pq and pq[0][1] < x:\n",
    "                heapq.heappop(pq)\n",
    "\n",
    "            if pq:\n",
    "                ans[j] = pq[0][0]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        n, m = len(intervals), len(queries)\n",
    "        intervals.sort()\n",
    "        queries = sorted((x, i) for i, x in enumerate(queries))\n",
    "        ans = [-1] * m\n",
    "        pq = []\n",
    "        i = 0\n",
    "        for x, j in queries:\n",
    "            while i < n and intervals[i][0] <= x:\n",
    "                a, b = intervals[i]\n",
    "                heappush(pq, (b - a + 1, b))\n",
    "                i += 1\n",
    "            while pq and pq[0][1] < x:\n",
    "                heappop(pq)\n",
    "            if pq:\n",
    "                ans[j] = pq[0][0]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        n , m = len(intervals) , len(queries)\n",
    "        intervals.sort()\n",
    "        queries = sorted((x,i) for i ,x in enumerate(queries))\n",
    "        ans = [-1] * m\n",
    "        pq = []\n",
    "        i = 0\n",
    "        for x, j in queries:\n",
    "            while i < n and intervals[i][0] <= x:\n",
    "                a , b = intervals[i]\n",
    "                heappush(pq,(b - a + 1 , b))\n",
    "                i += 1\n",
    "            while pq and pq[0][1] < x:\n",
    "                heappop(pq)\n",
    "            if pq:\n",
    "                ans[j] = pq[0][0]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        li, lq = len(intervals), len(queries)\n",
    "        intervals.sort()\n",
    "        tmp = [(queries[i], i) for i in range(lq)]\n",
    "        tmp.sort()\n",
    "        ans = [0] * lq\n",
    "        start = 0\n",
    "        q = []\n",
    "        for t in range(len(tmp)):\n",
    "            qi, i = tmp[t][0], tmp[t][1]\n",
    "            if start < li and intervals[start][0] <= qi:\n",
    "                while start < li and intervals[start][0] <= qi:\n",
    "                    heapq.heappush(q, (intervals[start][1] - intervals[start][0] + 1, intervals[start][1]))\n",
    "                    start += 1\n",
    "            if len(q) == 0:\n",
    "                ans[i] = -1\n",
    "                continue\n",
    "            while len(q) > 0:\n",
    "                lengthi, righti = heapq.heappop(q)\n",
    "                if righti >= qi:\n",
    "                    ans[i] = lengthi\n",
    "                    heapq.heappush(q, (lengthi, righti))\n",
    "                    break\n",
    "            if ans[i] == 0:\n",
    "                ans[i] = -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        n, m = len(intervals), len(queries)\n",
    "        intervals.sort()\n",
    "        queries = sorted((x, i) for i, x in enumerate(queries))\n",
    "        ans = [-1] * m\n",
    "        pq = []\n",
    "        i = 0\n",
    "        for x, j in queries:\n",
    "            while i < n and intervals[i][0] <= x:\n",
    "                a, b = intervals[i]\n",
    "                heappush(pq, (b - a + 1, b))\n",
    "                i += 1\n",
    "            while pq and pq[0][1] < x:\n",
    "                heappop(pq)\n",
    "            if pq:\n",
    "                ans[j] = pq[0][0]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        n, m = len(intervals), len(queries)\n",
    "        intervals.sort()\n",
    "        queries = sorted((x, i) for i, x in enumerate(queries))\n",
    "        ans = [-1] * m\n",
    "        pq = []\n",
    "        i = 0\n",
    "        for x, j in queries:\n",
    "            while i < n and intervals[i][0] <= x:\n",
    "                a, b = intervals[i]\n",
    "                heappush(pq, (b - a + 1, b))\n",
    "                i += 1\n",
    "            while pq and pq[0][1] < x:\n",
    "                heappop(pq)\n",
    "            if pq:\n",
    "                ans[j] = pq[0][0]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        n, m = len(intervals), len(queries)\n",
    "        intervals.sort()\n",
    "        queries = sorted((x, i) for i, x in enumerate(queries))\n",
    "        ans = [-1] * m\n",
    "        pq = []\n",
    "        i = 0\n",
    "        for x, j in queries:\n",
    "            while i < n and intervals[i][0] <= x:\n",
    "                a, b = intervals[i]\n",
    "                heappush(pq, (b - a + 1, b))\n",
    "                i += 1\n",
    "            while pq and pq[0][1] < x:\n",
    "                heappop(pq)\n",
    "            if pq:\n",
    "                ans[j] = pq[0][0]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        n = len(intervals)\n",
    "        m = len(queries)\n",
    "        intervals.sort()\n",
    "        queries = sorted((query, i) for i, query in enumerate(queries))\n",
    "        ans = [-1 for _ in range(m)]\n",
    "        priorityq = []\n",
    "        i = 0\n",
    "        for query, j in queries:\n",
    "            while i < n and intervals[i][0] <= query:\n",
    "                left, right = intervals[i]\n",
    "                heappush(priorityq, (right-left+1, right))\n",
    "                i += 1\n",
    "            while priorityq and priorityq[0][1] < query:\n",
    "                heappop(priorityq)\n",
    "            \n",
    "            if priorityq:\n",
    "                ans[j] = priorityq[0][0]\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        n, m = len(intervals), len(queries)\n",
    "        intervals.sort()\n",
    "        queries = sorted((x, i) for i, x in enumerate(queries))\n",
    "        ans = [-1] * m\n",
    "        pq = []\n",
    "        i = 0\n",
    "        for x, j in queries:\n",
    "            while i < n and intervals[i][0] <= x:\n",
    "                a, b = intervals[i]\n",
    "                heappush(pq, (b - a + 1, b))\n",
    "                i += 1\n",
    "            while pq and pq[0][1] < x:\n",
    "                heappop(pq)\n",
    "            if pq:\n",
    "                ans[j] = pq[0][0]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        n, m = len(intervals), len(queries)\n",
    "        intervals.sort()\n",
    "        queries = sorted((x, i) for i, x in enumerate(queries))\n",
    "        #print(queries)\n",
    "        ans = [-1] * m\n",
    "        pq = []\n",
    "        i = 0 # index for intervals\n",
    "        for x, j in queries:\n",
    "            #print(x,j)\n",
    "            while i < n and intervals[i][0] <= x:\n",
    "                a, b = intervals[i]\n",
    "                heappush(pq, (b - a + 1, b))\n",
    "                i += 1\n",
    "            #print(\"first while: \"+str(pq))\n",
    "            while pq and pq[0][1] < x:\n",
    "                heappop(pq)\n",
    "            #print(\"second while: \"+str(pq))\n",
    "            if pq:\n",
    "                ans[j] = pq[0][0]\n",
    "           # print(\"final: \"+str(pq))\n",
    "        return ans\n",
    "\n",
    "        # n = len(queries)\n",
    "        # dp = [inf]*n\n",
    "\n",
    "        # for left,right in intervals:\n",
    "        #     for i in range(n):\n",
    "        #         if left<=queries[i] and queries[i]<=right:\n",
    "        #             dp[i] = min(dp[i],right-left+1)\n",
    "\n",
    "        # #print(dp)\n",
    "        # #replace inf with -1\n",
    "        # dp = [-1 if x == inf else x for x in dp ]\n",
    "        # return dp\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        n, m = len(intervals), len(queries)\n",
    "        intervals.sort()\n",
    "        queries = sorted((x, i) for i, x in enumerate(queries))\n",
    "        ans = [-1] * m\n",
    "        pq = []\n",
    "        i = 0\n",
    "        for x, j in queries:\n",
    "            while i < n and intervals[i][0] <= x:\n",
    "                a, b = intervals[i]\n",
    "                heappush(pq, (b - a + 1, b))\n",
    "                i += 1\n",
    "            while pq and pq[0][1] < x:\n",
    "                heappop(pq)\n",
    "            if pq:\n",
    "                ans[j] = pq[0][0]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        intervals.sort()\n",
    "        queries = sorted([(q,i) for i , q in enumerate(queries)])\n",
    "        n = len(intervals)\n",
    "        ans = [-1] * len(queries)\n",
    "        i = 0\n",
    "        queue = []\n",
    "        for x , idx in queries:\n",
    "            while i < n and intervals[i][0] <= x:\n",
    "                heapq.heappush(queue,(intervals[i][1] - intervals[i][0] + 1,intervals[i][1]))\n",
    "                i += 1\n",
    "            while queue and queue[0][1] < x:\n",
    "                heapq.heappop(queue)\n",
    "            if queue:\n",
    "                ans[idx] = queue[0][0]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        n, m = len(intervals), len(queries)\n",
    "        intervals.sort()\n",
    "        queries = sorted((x, i) for i, x in enumerate(queries))\n",
    "        ans = [-1] * m\n",
    "        pq = []\n",
    "        i = 0\n",
    "        for x, j in queries:\n",
    "            while i < n and intervals[i][0] <= x:\n",
    "                a, b = intervals[i]\n",
    "                if b >= x:\n",
    "                    heappush(pq, (b - a + 1, b))\n",
    "                i += 1\n",
    "            while pq and pq[0][1] < x:\n",
    "                heappop(pq)\n",
    "            if pq:\n",
    "                ans[j] = pq[0][0]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        n, m = len(intervals), len(queries)\n",
    "        intervals.sort()\n",
    "        queries = sorted([(v, i) for i, v in enumerate(queries)])\n",
    "        res = [-1] * m\n",
    "        heap = []\n",
    "        i = 0\n",
    "        for v, idx in queries:\n",
    "            while i < n and intervals[i][0] <= v:\n",
    "                heapq.heappush(heap, (intervals[i][1] - intervals[i][0] + 1, intervals[i][1]))\n",
    "                i += 1\n",
    "            while heap and heap[0][1] < v:\n",
    "                heapq.heappop(heap)\n",
    "            if heap:\n",
    "                res[idx] = heap[0][0]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        intervals.sort(key=lambda x: x[0])\n",
    "        query_positions = [(q, i) for i, q in enumerate(queries)]\n",
    "        query_positions.sort(key=lambda x: x[0])\n",
    "        \n",
    "        heap = []\n",
    "        j = 0\n",
    "        result = [-1] * len(queries)\n",
    "        \n",
    "        for q, i in query_positions:\n",
    "            while j < len(intervals) and intervals[j][0] <= q:\n",
    "                l, r = intervals[j]\n",
    "                length = r - l + 1\n",
    "                heapq.heappush(heap, (length, l, r))\n",
    "                j += 1\n",
    "                \n",
    "            while heap and heap[0][2] < q:\n",
    "                heapq.heappop(heap)\n",
    "                \n",
    "            if heap:\n",
    "                result[i] = heap[0][0]\n",
    "        \n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        intervals.sort()\n",
    "        lint = len(intervals)\n",
    "        n = len(queries)\n",
    "        lst = list(range(n))\n",
    "        lst.sort(key=lambda i:queries[i])\n",
    "        left = 0\n",
    "        q = []\n",
    "        ret = [0] * n\n",
    "        for i in range(n):\n",
    "            qid = lst[i]\n",
    "            k = queries[qid]\n",
    "            while left < lint and intervals[left][0] <= k:\n",
    "                if intervals[left][1] >= k:\n",
    "                    heappush(q, [intervals[left][1] - intervals[left][0], left])\n",
    "                left += 1\n",
    "            # print(qid, k, q)\n",
    "            while q and intervals[q[0][1]][1] < k:\n",
    "                heappop(q)\n",
    "            if not q:\n",
    "                ret[qid] = -1\n",
    "            else:\n",
    "                ret[qid] = q[0][0] + 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        intervals.sort()\n",
    "        lint = len(intervals)\n",
    "        n = len(queries)\n",
    "        lst = list(range(n))\n",
    "        lst.sort(key=lambda i:queries[i])\n",
    "        left = 0\n",
    "        q = []\n",
    "        ret = [0] * n\n",
    "        for i in range(n):\n",
    "            qid = lst[i]\n",
    "            \n",
    "            k = queries[qid]\n",
    "            while left < lint and intervals[left][0] <= k:\n",
    "                # if intervals[left][1] >= k:\n",
    "                heappush(q, [intervals[left][1] - intervals[left][0], left])\n",
    "                left += 1\n",
    "            # print(qid, k, q)\n",
    "            while q and intervals[q[0][1]][1] < k:\n",
    "                heappop(q)\n",
    "            if not q:\n",
    "                ret[qid] = -1\n",
    "            else:\n",
    "                ret[qid] = q[0][0] + 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        res = defaultdict(int)\n",
    "        intervals.sort()\n",
    "        hq = []\n",
    "        heapq.heapify(hq)\n",
    "        i = 0\n",
    "        n = len(intervals)\n",
    "        for q in sorted(queries):\n",
    "            while i < n and intervals[i][0] <= q:\n",
    "                heapq.heappush(hq, (intervals[i][1] - intervals[i][0] + 1, i))\n",
    "                i += 1\n",
    "            while hq and intervals[hq[0][1]][1] < q:\n",
    "                heapq.heappop(hq)\n",
    "            if not hq:\n",
    "                res[q] = -1\n",
    "            else:\n",
    "                res[q] = hq[0][0]\n",
    "                    \n",
    "        return [res[q] for q in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, n) -> None:\n",
    "        self.fa = [i for i in range(n)]\n",
    "        # self.count = n\n",
    "\n",
    "\n",
    "    def find(self, x):\n",
    "        if x != self.fa[x]:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "        # x_copy = x\n",
    "        # while x_copy != self.fa[x_copy]:\n",
    "        #     x_copy  = self.fa[x_copy]\n",
    "        # root= x_copy\n",
    "        # x_copy = x\n",
    "        # while x_copy != root:\n",
    "        #     self.fa[x_copy] = root\n",
    "        #     x_copy = self.fa[x_copy]\n",
    "\n",
    "        # return self.fa[x]\n",
    "    \n",
    "    \n",
    "    def merge(self, x, y):\n",
    "        self.fa[x] = self.find(y)\n",
    "        # self.count -= 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(intervals), len(queries)\n",
    "\n",
    "        intervals.sort(key=lambda x: x[1] - x[0])\n",
    "        queries = SortedList([(q, i) for i, q in enumerate(queries)])\n",
    "\n",
    "        dsu = DSU(n+1)\n",
    "\n",
    "\n",
    "        ans = [-1] * n\n",
    "\n",
    "        for l, r in intervals:\n",
    "            length = r - l + 1\n",
    "            pos = queries.bisect_left((l, -1))\n",
    "\n",
    "            idx = dsu.find(pos)\n",
    "            while idx < n and queries[idx][0] <= r:\n",
    "                ans[queries[idx][1]] = length\n",
    "                dsu.merge(idx, idx+1)\n",
    "                idx = dsu.find(idx + 1)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        heap = []\n",
    "        intervals.sort()\n",
    "        res = [-1]*len(queries)\n",
    "        sortedQuery = sorted(enumerate(queries), key=lambda x:x[1])\n",
    "        curIdx = 0\n",
    "        for idx, val in sortedQuery:\n",
    "            while curIdx < len(intervals) and intervals[curIdx][0] <= val:\n",
    "                heapq.heappush(heap, [intervals[curIdx][1]-intervals[curIdx][0]+1, intervals[curIdx][1]])\n",
    "                curIdx += 1\n",
    "            while len(heap) > 0 and heap[0][1] < val:\n",
    "                heapq.heappop(heap)\n",
    "            res[idx] = heap[0][0] if len(heap) > 0 else -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, n) -> None:\n",
    "        self.fa = [i for i in range(n)]\n",
    "        # self.count = n\n",
    "\n",
    "\n",
    "    def find(self, x):\n",
    "        if x != self.fa[x]:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "        # x_copy = x\n",
    "        # while x_copy != self.fa[x_copy]:\n",
    "        #     x_copy  = self.fa[x_copy]\n",
    "        # root= x_copy\n",
    "        # x_copy = x\n",
    "        # while x_copy != root:\n",
    "        #     self.fa[x_copy] = root\n",
    "        #     x_copy = self.fa[x_copy]\n",
    "\n",
    "        # return self.fa[x]\n",
    "    \n",
    "    \n",
    "    def merge(self, x, y):\n",
    "        self.fa[x] = self.find(y)\n",
    "        # self.count -= 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(intervals), len(queries)\n",
    "\n",
    "        intervals.sort(key=lambda x: x[1] - x[0])\n",
    "        queries = sorted([(q, i) for i, q in enumerate(queries)])\n",
    "\n",
    "        dsu = DSU(n+1)\n",
    "\n",
    "\n",
    "        ans = [-1] * n\n",
    "\n",
    "        for l, r in intervals:\n",
    "            length = r - l + 1\n",
    "            pos = bisect_left(queries, (l, -1))\n",
    "\n",
    "            idx = dsu.find(pos)\n",
    "            while idx < n and queries[idx][0] <= r:\n",
    "                ans[queries[idx][1]] = length\n",
    "                dsu.merge(idx, idx+1)\n",
    "                idx = dsu.find(idx + 1)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, n) -> None:\n",
    "        self.fa = [i for i in range(n)]\n",
    "        # self.count = n\n",
    "\n",
    "\n",
    "    def find(self, x):\n",
    "        if x != self.fa[x]:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "        # x_copy = x\n",
    "        # while x_copy != self.fa[x_copy]:\n",
    "        #     x_copy  = self.fa[x_copy]\n",
    "        # root= x_copy\n",
    "        # x_copy = x\n",
    "        # while x_copy != root:\n",
    "        #     self.fa[x_copy] = root\n",
    "        #     x_copy = self.fa[x_copy]\n",
    "\n",
    "        # return self.fa[x]\n",
    "    \n",
    "    \n",
    "    def merge(self, x, y):\n",
    "        self.fa[x] = self.find(y)\n",
    "        # self.count -= 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        queries = [ (n, i) for i, n in enumerate(queries)]\n",
    "        intervals.sort(key=lambda x:x[1]-x[0])\n",
    "        queries_bk = SortedList(queries)\n",
    "        n = len(queries)\n",
    "        dsu = DSU(n+1)\n",
    "        ans = [-1]*n\n",
    "        for l, r in intervals:\n",
    "       \n",
    "            q = queries_bk.bisect_left((l, -1))\n",
    "            q = dsu.find(q)\n",
    "            while q < n and queries_bk[q][0] <= r:\n",
    "                ans[queries_bk[q][1]] = r - l + 1\n",
    "                dsu.merge(q, q+1)\n",
    "                q = dsu.find(q+1)\n",
    "                # q += 1\n",
    "               \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(intervals), len(queries)\n",
    "\n",
    "        intervals.sort(key=lambda x: x[1] - x[0])\n",
    "        queries = sorted([(q, i) for i, q in enumerate(queries)])\n",
    "\n",
    "        fa = list(range(n + 1))\n",
    "\n",
    "        def find(x):\n",
    "            if x != fa[x]:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "\n",
    "        ans = [-1] * n\n",
    "\n",
    "        for l, r in intervals:\n",
    "            length = r - l + 1\n",
    "            pos = bisect_left(queries, (l, -1))\n",
    "\n",
    "            idx = find(pos)\n",
    "            while idx < n and queries[idx][0] <= r:\n",
    "                ans[queries[idx][1]] = length\n",
    "                fa[idx] = idx + 1\n",
    "                idx = find(idx + 1)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(intervals), len(queries)\n",
    "\n",
    "        intervals.sort(key=lambda x: x[1] - x[0])\n",
    "        queries = sorted([(q, i) for i, q in enumerate(queries)])\n",
    "\n",
    "        fa = list(range(n + 1))\n",
    "\n",
    "        def find(x):\n",
    "            if x != fa[x]:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "\n",
    "        ans = [-1] * n\n",
    "\n",
    "        for l, r in intervals:\n",
    "            length = r - l + 1\n",
    "            pos = bisect_left(queries, (l, -1))\n",
    "\n",
    "            idx = find(pos)\n",
    "            while idx < n and queries[idx][0] <= r:\n",
    "                ans[queries[idx][1]] = length\n",
    "                fa[idx] = idx + 1\n",
    "                idx = find(idx + 1)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "#         f = [-1]*len(queries)\n",
    "#         d = defaultdict(list)\n",
    "#         for i,j in enumerate(queries):\n",
    "#             d[j].append(i)\n",
    "#         intervals.sort(key=lambda x:x[1]-x[0])\n",
    "#         q = sorted(set(queries))\n",
    "#         for s,e in intervals:\n",
    "#             ts = bisect_left(q,s)\n",
    "#             te = bisect_right(q,e)\n",
    "#             tl = e-s+1\n",
    "#             if te>ts:\n",
    "#                 for i in range(ts,te):\n",
    "#                     target = q.pop(ts)\n",
    "#                     for i in d[target]:\n",
    "#                         f[i] = tl\n",
    "#         return f\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(intervals), len(queries)\n",
    "\n",
    "        intervals.sort(key=lambda x: x[1] - x[0])\n",
    "        queries = sorted([(q, i) for i, q in enumerate(queries)])\n",
    "\n",
    "        fa = list(range(n + 1))\n",
    "\n",
    "        def find(x):\n",
    "            if x != fa[x]:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "\n",
    "        ans = [-1] * n\n",
    "        # print(queries)\n",
    "        for l, r in intervals:\n",
    "            length = r - l + 1\n",
    "            pos = bisect_left(queries, (l, -1))\n",
    "            # print(fa)\n",
    "            # print(pos, find(pos))\n",
    "            idx = find(pos)\n",
    "            while idx < n and queries[idx][0] <= r:\n",
    "                ans[queries[idx][1]] = length\n",
    "                fa[idx] = idx + 1\n",
    "                idx = find(idx + 1)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        qs = sorted((q, i) for i, q in enumerate(queries))\n",
    "        intervals.sort(key=lambda x: x[1] - x[0])\n",
    "        n, m = len(intervals), len(queries)\n",
    "        res = [-1] * m \n",
    "\n",
    "        fa = list(range(m + 1))\n",
    "        def find(x):\n",
    "            if x != fa[x]:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        \n",
    "        for left, right in intervals:\n",
    "            length = right - left + 1\n",
    "            j = bisect_left(qs, (left, -1))\n",
    "            j = find(j)\n",
    "            while j < m and qs[j][0] <= right:\n",
    "                res[qs[j][1]] = length\n",
    "                fa[j] = j + 1\n",
    "                j = find(j + 1)\n",
    "        return res\n",
    "\n",
    "        # qs = sorted((q, i) for i, q in enumerate(queries))\n",
    "        # intervals.sort()\n",
    "        # n, m = len(intervals), len(queries)\n",
    "        # res = [-1] * m\n",
    "        # h = []\n",
    "        # i = 0\n",
    "        # for q, qi in qs:\n",
    "        #     while i < n and intervals[i][0] <= q:\n",
    "        #         a, b = intervals[i]\n",
    "        #         heappush(h, (b - a + 1, b))\n",
    "        #         i += 1\n",
    "        #     while h and h[0][1] < q:\n",
    "        #         heappop(h)\n",
    "        #     if h:\n",
    "        #         res[qi] = h[0][0]\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        f = [-1]*len(queries)\n",
    "        d = defaultdict(list)\n",
    "        for i,j in enumerate(queries):\n",
    "            d[j].append(i)\n",
    "        intervals.sort(key=lambda x:x[1]-x[0])\n",
    "        q = sorted(set(queries))\n",
    "        for s,e in intervals:\n",
    "            ts = bisect_left(q,s)\n",
    "            te = bisect_right(q,e)\n",
    "            tl = e-s+1\n",
    "            if te>ts:\n",
    "                for i in range(ts,te):\n",
    "                    target = q.pop(ts)\n",
    "                    for i in d[target]:\n",
    "                        f[i] = tl\n",
    "        return f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        f = [-1]*len(queries)\n",
    "        d = defaultdict(list)\n",
    "        for i,j in enumerate(queries):\n",
    "            d[j].append(i)\n",
    "        intervals.sort(key=lambda x:x[1]-x[0])\n",
    "        q = sorted(set(queries))\n",
    "        for s,e in intervals:\n",
    "            ts = bisect_left(q,s)\n",
    "            te = bisect_right(q,e)\n",
    "            tl = e-s+1\n",
    "            if te>ts:\n",
    "                for i in range(ts,te):\n",
    "                    target = q.pop(ts)\n",
    "                    for i in d[target]:\n",
    "                        f[i] = tl\n",
    "        return f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        f = [-1]*len(queries)\n",
    "        d = defaultdict(list)\n",
    "        for i,j in enumerate(queries):\n",
    "            d[j].append(i)\n",
    "        intervals.sort(key=lambda x:x[1]-x[0])\n",
    "        q = sorted(set(queries))\n",
    "        for s,e in intervals:\n",
    "            ts = bisect_left(q,s)\n",
    "            te = bisect_right(q,e)\n",
    "            tl = e-s+1\n",
    "            if te>ts:\n",
    "                for i in range(ts,te):\n",
    "                    target = q.pop(ts)\n",
    "                    for i in d[target]:\n",
    "                        f[i] = tl\n",
    "        return f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        n = len(queries)\n",
    "        pa = list(range(n+1))\n",
    "        def find(x):\n",
    "            if pa[x] != x:\n",
    "                pa[x] = find(pa[x])\n",
    "            return pa[x]\n",
    "        qu = sorted((x,i) for i,x in enumerate(queries))\n",
    "        ans = [-1] * n\n",
    "        for l,a,b in sorted((b-a+1,a,b) for a,b in intervals):\n",
    "            i = find(bisect_left(qu,(a,)))\n",
    "            while i < n and qu[i][0] <= b:\n",
    "                pa[i] = i+1\n",
    "                ans[qu[i][1]] = l\n",
    "                i = find(i)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
